Metrics are numbers associated with a telecommunications network that allow comparison of various paths connecting the same pair of source-destination routers. In U.S. Pat. No. 4,905,233 to Cain et al., there is a disclosed use of path metrics for establishing a transmission route between a source node and a destination node in a multinode communications network. The method involves monitoring transmission characteristics of each of the transmission paths among the respective nodes of the network so as to derive a plurality of path metrics representative of the ability of the respective transmission paths of the network to transmit communication signals. Then, feasible transmission routes to be used for the transmission of communication signals from the source node to the destination node are selected as those routes which extend from the source node to the destination node and each of which is comprised of one or more transmission paths among the nodes of the network and the sum of path metrics of transmission paths from neighboring nodes to the destination node is less than the path metric of a transmission path the end nodes of which corresponds to the source and destination nodes. Communication signals are then transmitted from the source node to the destination node over the selected feasible transmission routes.
For a different example, consider FIG. 1 where path comprises a set of links 130 connecting a pair of source-destination routers 120. A designer selects the metrics so that traffic load takes the most efficient path defined by the minimum path metric. Routers 120 can actually evaluate the metric of the entire path connecting a pair of source-destination routers 120. Routing algorithms can compute a metric as a value that applies to an end-to-end path. With this use, metrics allow comparisons of the paths to the same destination router 120. Another use of metrics is to determine the cost associated with outgoing links 130 from a router 120. In many routing algorithms, the end-to-end metric (path metric) is the sum of link metrics.
Prior art routing protocols use different methods of computing the metric. Some, like Routing Information Protocol (RIP), count the hops (number of routers 120 on the path) between the pair of source-destination routers 120. Others have no standard way of computing a metric, making its computation a local choice. Factors used in computing metrics include the following: 1. link bandwidth; 2. link delay; 3. administrative preference, such as monetary cost; 4. link error rate; 5. link utilization. Not all these factors are useful in real networks. In particular, improper use of link utilization in link metrics may create path oscillation. For instance, suppose there is traffic load on Path 1 (not shown) to a destination. Then, Path 2 (not shown) is created and also has connectivity to the same destination. Assume that both Paths 1 and 2 have equal bandwidth. Path 2 becomes more attractive than the more heavily loaded Path 1. Traffic load then migrates to Path 2, making Path 1 less loaded and now more attractive than more heavily loaded Path 2. This leads to the best path choice alternating between Path 1 and Path 2.
Metrics are generally comparable only within the same dynamic routing protocol. RIP uses hop count, whereas IGPR (Interior Gateway Routing Protocol) and EIGPR (Enhanced IGPR) use the same complex formula that, in practice, generally is bandwidth based. OSPF (Open Shortest Path First) use an arbitrary interface cost that, in practice, like IGPR and EIGPR, is bandwidth based.
Consider now the prior art network of FIG. 2, each node 210 in network 200 can communicate with only one of its neighboring nodes 210 at any one time. For instance, assuming Node 4 has a bandwidth of 100 Mbps, the sum of the communication rates (in Mbps) at which Node 4 communicates with its neighboring Nodes 1, 2, 5, and 6 must be 100 Mbps or less. This means that a traffic load from Node 1 to Node 5 via Node 4 affects the bandwidth left for another traffic load from Node 2 to Node 6 via Node 4, and vice versa. Specifically, if Node 4 uses 40 Mbps of its bandwidth to receive packets from Node 2 and another 40 Mbps of it bandwidth to forward the packets to Node 6, it has only 20 Mbps of bandwidth left to handle traffic load from Node 1 to Node 5. It may use 10 Mbps of the remaining bandwidth of 20 Mbps to receive packets from Node 1 and uses the last 10 Mbps of its available bandwidth to forward the packets to Node 5.
For network 200, typical metric assignments of the prior art would have disadvantages. First, a hop count metric does not reflect the merit of the path. For example, assuming Node 4 uses 40 Mbps of its bandwidth of 100 Mbps for receiving packets from Node 2 and uses 40 Mbps for forwarding the packets to Node 6, if Node 1 wants to send a flow at 40 Mbps to Node 5, relying on hop count metrics, it will split the load 50—50 between the two paths via Node 3 and Node 4, assuming load balancing is applicable here. This means that Node 4 uses its last 20 Mbps of bandwidth for receiving packets from Node 1. With input rate at 60 Mbps (40 Mbps from Node 2 and 20 Mbps from Node 1) and output rate at only 40 Mbps (to Node 6), Node 4 has to use a buffer to store packets for later forwarding to Node 5. Soon, the queue in this buffer will overflow and Node 4 has to drop packets. This is called node congestion. Therefore, hop count metrics do not reflect the need for Node 1 to divert its traffic load to Node 3.
Secondly, metric assignments based on link bandwidth also have disadvantages if applied to network 200. Assuming that link 1-4 (connecting Node 1 and Node 4) and link 4-5 (connecting Node 4 and Node 5) have very high bandwidth, and therefore, have low metrics, it follows that the path from Node 1 to Node 5 via Node 4 will be preferred. However, in network 200 of the present invention, Node 4 is the limiting factor, not links 1-4 and 4-5. Typical metrics for links 1-4 and 4-5 will not change and hence path metric for the path including these two links will also not change even when Node 4 runs out of bandwidth handling traffic load from Node 2 to Node 6 via Node 4. As a result, if Node 1 wants to send a flow at 40 Mbps to Node 5, the path via Node 4 is an attractive one, while the path is in fact congested at Node 4.
In patent application Ser. No. 09/187,665, filed Nov. 5, 1998, incorporated by reference, corresponding to published PCT application WO 00/25485, published May 4, 2000, owned by the assignee of the present invention a wireless mesh network is described with reference to FIG. 3, similar to FIG. 1, having fully mutually interconnected, line-of-sight nodes 12–19. All nodes need not be interconnected, so long as a node has line of sight communication with at least one neighbor, with the neighbor being in line of sight communication with the rest of the network on the same basis. Communication between nodes is by packets using a protocol whose basic features are described in patent application Ser. No. 09/328,105, filed Jun. 8, 1999, incorporated by reference herein and owned by the assignee of the present invention. In the protocol described therein, time is broken up into frames of known length. In each frame, every node has scheduled slots with which to exchange control information with each of its neighbor nodes, the slots forming a control channel. Any time a node is not participating in a control channel transmission or reception, it is free to schedule the transmission or reception of data packets. As part of the control channel, requests are made to transmit bits. As part of the request, information about unscheduled periods, i.e. available time or gaps, in the requesting node's data channel is transmitted. The node receiving the requests to transmit (RTS) grants or denies transmissions. Part of the grant includes a schedule, selected from the requester's schedule, for when to transmit the data.
The media access control layer (MAC layer) is the interface between the link layer that generates and consumes the payload data units (PDUs) and the physical layer that is responsible for the actual transmission. The general principle of the MAC protocol is that each pair of neighbors must communicate control information on a regular basis in order to schedule data transmissions. Thus, there is the concept of a frame. During every frame, a node communicates with each of its neighbors making requests to send (RTS) and making grants of clear to send (CTS). The time spent transmitting and receiving this control information is called the control channel. Data transmissions are interwoven throughout the frame, avoiding the control channel. The performance of the MAC scheduling depends on the following factors: (1) the length of the frame, (2) the percent of the frame taken up by the control channel, (3) the efficiency of scheduling data around the control channel, (4) the efficiency of scheduling data transmissions between neighboring nodes. What is needed is a path metric system which takes advantage of fully scheduled transmissions to and from neighboring nodes.
An object of the present invention is to provide a new metric system to better guide the selection of the paths between any pair of source-destination routers given the availability of fully scheduled transmission to and from neighboring nodes.